import java.util.Queue;

import javax.management.Query;

import org.w3c.dom.Node;

/*
 * @lc app=leetcode.cn id=559 lang=java
 *
 * [559] N 叉树的最大深度
 */

// @lc code=start
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
// DFS效率最高，但也有点抽象。
class Solution {
    public int maxDepth(Node root) {  //层序遍历解法
        if(root == null)
            return 0;
        if(root.children.size() == 0)
            return 1;
        int depth = 0;
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while(!queue.isEmpty()){
            int count = queue.size();//它这里先记录了队列的初始长度
            depth++;
            while(count > 0){//然后这样可以吧一层的节点都遍历完
                Node node = queue.poll();
                if(node.children.size() != 0)
                    queue.addAll(node.children);              
                count--;                
            }
        }
        return depth;        
    }

    public int maxDepth2(Node root) {//DFS递归写法
        if(root == null)//结束条件
            return 0;
        int depth = 0;

        for(int i = 0;i<root.children.size();i++){
            depth = Math.max(depth,maxDepth(root.children.get(i)));
        }
        return depth+1;//这个一定要加一，代表深了一层
    }

    public int maxDepth1(Node root) {//层次遍历，用了双队列，用一个队列空来判断一层结束了。
        int max = 0;
        //用队列层次遍历？没往下一层直接+1？
        if(root == null) return 0;
        Queue<Node> q1 = new LinkedList<>();
        Queue<Node> q2 = new LinkedList<>();
        q1.add(root);
        while(!(q1.isEmpty()&&q2.isEmpty())  ){
            if(q2.isEmpty()){
                max++;
                while (!q1.isEmpty()){
                    q2.addAll(q1.poll().children);
                }
            }
            else if(q1.isEmpty()){
                max++;
                while (!q2.isEmpty()) {
                    q1.addAll(q2.poll().children);
                }
            }
        }
        return max;
    }
}
// @lc code=end

